package leetcode.year2021.month11;

import java.util.LinkedList;

// 394. 字符串解码
public class _15_2DecodeString394 {
  public static void main(String[] args) {
    String str = "3[a]2[bc]";
    decodeString(str);
  }
  public static String decodeString(String s) {
    // 解题思路，在于每个中括号前面的数字和中括号中的元素，表示循环输出该中括号中的元素几次，其余正常输出, 遇到数字，则有括号
    // 应该使用递归的方式求解，因为当遇到括号的时候，应该通过递归求取括号中的值（或者栈）
    // 首先使用递归的写法
    StringBuilder resBuilder = new StringBuilder();
    decodeDfs(s,resBuilder);
    return resBuilder.toString();
  }

  // 递归方法，每次遇到[]则将[]中的元素递归求值
  private static void decodeDfs(String s, StringBuilder resBuilder) {
    // 遍历s, 没遇到括号就追加结果，遇到括号就循环 -> 递归求值
    // 使用一个栈来求取[]中的字符串，并使用该值递归
    int point = 0;
    while (point < s.length()){
      if (Character.isDigit(s.charAt(point))){
        // 如果是数字，则记录当前数字是多少，然后拿到后面中括号中的值，然后将point移到中括号结束后一行
        // 寻找记录当前数字
        StringBuffer tempNumStr = new StringBuffer();
        tempNumStr.append(s.charAt(point));
        while (Character.isDigit(s.charAt(point+1))){
          tempNumStr.append(s.charAt(point+1));
          point++;
        }
        // 已经到了中括号的位置，继续寻找中括号中的值
        LinkedList<Character> stack = new LinkedList<>();
        stack.addFirst('[');
        StringBuffer loopStr = new StringBuffer();
        point += 2;
        while (!stack.isEmpty()){
          if (s.charAt(point) == '['){
            stack.addFirst('[');
          }
          if (s.charAt(point) == ']'){
            stack.removeFirst();
          }
          loopStr.append(s.charAt(point));
          point++;
        }
        loopStr.deleteCharAt(loopStr.length() - 1);
        for (int i = 0; i < Integer.valueOf(tempNumStr.toString()); i++) {
          decodeDfs(loopStr.toString(),resBuilder);
        }
      } else {
        resBuilder.append(s.charAt(point));
        point++;
      }
    }
  }


  /**
   * 394. 字符串解码
   * 给定一个经过编码的字符串，返回它解码后的字符串。
   *
   * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
   *
   * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
   *
   * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
   *
   *
   *
   * 示例 1：
   *
   * 输入：s = "3[a]2[bc]"
   * 输出："aaabcbc"
   * 示例 2：
   *
   * 输入：s = "3[a2[c]]"
   * 输出："accaccacc"
   * 示例 3：
   *
   * 输入：s = "2[abc]3[cd]ef"
   * 输出："abcabccdcdcdef"
   * 示例 4：
   *
   * 输入：s = "abc3[cd]xyz"
   * 输出："abccdcdcdxyz"
   */
}
